package com.leetcode.algorithm.y22.m08.w5;

/**
 * 
 * 376. 摆动序列
 * 
 * https://leetcode.cn/problems/wiggle-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question0376Solution02 {

	// 贪心算法
	public int wiggleMaxLength(int[] nums) {
		// 前提条件：
		// 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
		// 全局最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
		int len = nums.length;
		int left = 0;
		while (left < len - 1 && nums[left] == nums[left + 1]) {
			left++;
		}
		int newLen = len - left;
		if (newLen <= 2) {
			return newLen;
		}

		int maxLen = 2;
		boolean isAsc = nums[left + 1] - nums[left] > 0;
		for (int i = left + 2; i < len; i++) {
			if ((isAsc && nums[i] - nums[i - 1] < 0) || (!isAsc && nums[i] - nums[i - 1] > 0)) {
				maxLen++;
				isAsc = !isAsc;
			}
		}

		return maxLen;
	}
    
}